package com.lun.swordtowardoffer2.c05;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class GroupAnagrams {

	private static final int[] hash = {2, 3, 5, 7 , 11, 13, 17, 19, 23, 29, 31, 37, 41,//
			43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
	
	
	public List<List<String>> groupAnagram(String[] strs){
		
		Map<Long, List<String>> groups = new HashMap<>();
		
		for(String str : strs) {
			long product = 1;
			for(char ch : str.toCharArray()) {
				product *= hash[ch - 'a'];
			}
			groups.putIfAbsent(product, new LinkedList<>());
			groups.get(product).add(str);
		}
		
		return new LinkedList<List<String>>(groups.values());
	}
	
	public List<List<String>> groupAnagram2(String[] strs){
		Map<String, List<String>> groups = new HashMap<>();
		
		for(String str : strs) {
			char[] arr = str.toCharArray();
			Arrays.sort(arr);
			String newOne = new String(arr);
			groups.putIfAbsent(newOne, new LinkedList<>());
			groups.get(newOne).add(str);
		}
		
		return new LinkedList<List<String>>(groups.values());
	}
	
}
